{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Number of Pairs With Absolute Difference K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countKDifference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #差的绝对值为 K 的数对数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;，请你返回数对&nbsp;<code>(i, j)</code>&nbsp;的数目，满足&nbsp;<code>i &lt; j</code>&nbsp;且&nbsp;<code>|nums[i] - nums[j]| == k</code>&nbsp;。</p>\n",
    "\n",
    "<p><code>|x|</code>&nbsp;的值定义为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果&nbsp;<code>x &gt;= 0</code>&nbsp;，那么值为&nbsp;<code>x</code>&nbsp;。</li>\n",
    "\t<li>如果&nbsp;<code>x &lt; 0</code>&nbsp;，那么值为&nbsp;<code>-x</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,2,2,1], k = 1\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>差的绝对值为 1 的数对为：\n",
    "- [<em><strong>1</strong></em>,<em><strong>2</strong></em>,2,1]\n",
    "- [<em><strong>1</strong></em>,2,<em><strong>2</strong></em>,1]\n",
    "- [1,<em><strong>2</strong></em>,2,<em><strong>1</strong></em>]\n",
    "- [1,2,<em><strong>2</strong></em>,<em><strong>1</strong></em>]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,3], k = 3\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>没有任何数对差的绝对值为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [3,2,1,5,4], k = 2\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>差的绝对值为 2 的数对为：\n",
    "- [<em><strong>3</strong></em>,2,<em><strong>1</strong></em>,5,4]\n",
    "- [<em><strong>3</strong></em>,2,1,<em><strong>5</strong></em>,4]\n",
    "- [3,<em><strong>2</strong></em>,1,5,<em><strong>4</strong></em>]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 200</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 99</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-number-of-pairs-with-absolute-difference-k](https://leetcode.cn/problems/count-number-of-pairs-with-absolute-difference-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-number-of-pairs-with-absolute-difference-k](https://leetcode.cn/problems/count-number-of-pairs-with-absolute-difference-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,2,1]\\n1', '[1,3]\\n3', '[3,2,1,5,4]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countKDifference(self, nums: List[int], k: int) -> int:\n",
    "        count = Counter(nums)\n",
    "\n",
    "        nDiffs = 0\n",
    "        for n in count.keys():\n",
    "            if (n + k) in count:\n",
    "                nDiffs += count[n] * count[n + k]\n",
    "\n",
    "        return nDiffs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKDifference(self, nums: List[int], k: int) -> int:\n",
    "        c = Counter(nums)\n",
    "        cnt = 0\n",
    "        for num in c:\n",
    "            if num + k in c:\n",
    "                cnt += c[num] * c[num + k]\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKDifference(self, nums: List[int], k: int) -> int:\n",
    "        # nums.sort()\n",
    "        c = Counter(nums)\n",
    "        l_nums = list(c.keys())\n",
    "        len_l_nums = len(l_nums)\n",
    "        cnt = 0\n",
    "        for i,numi in enumerate(l_nums):\n",
    "            for j in range(i+1,len_l_nums):\n",
    "                numj = l_nums[j]\n",
    "                if abs(numi - numj) == k:\n",
    "                    cnt += c[numi] * c[numj]\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKDifference(self, nums: List[int], k: int) -> int:\n",
    "        res,n = 0,len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if abs(nums[i]-nums[j]) == k:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKDifference(self, nums: List[int], k: int) -> int:\n",
    "        return sum([\n",
    "            n1 < n2 and abs(v1-v2) == k\n",
    "            for n1, v1 in enumerate(nums)\n",
    "            for n2, v2 in enumerate(nums)\n",
    "        ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKDifference(self, nums: List[int], k: int) -> int:\n",
    "        return len([(i, j) for i in range(len(nums)-1) for j in range(i+1, len(nums)) if abs(nums[i]-nums[j])==k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKDifference(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = Counter()\n",
    "        for num in nums:\n",
    "            res += n[num + k] + n[num - k]\n",
    "            n[num] += 1\n",
    "        return res   \n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKDifference(self, nums: List[int], k: int) -> int:\n",
    "        c=collections.Counter(nums)\n",
    "        ret=0\n",
    "        for key in c:\n",
    "            ret+=c[key]*c[key+k]\n",
    "            ret+=c[key]*c[key-k]\n",
    "        return ret//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countKDifference(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        cnt = Counter()\n",
    "        for num in nums:\n",
    "            res += cnt[num - k] + cnt[num + k]\n",
    "            cnt[num] += 1\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
